Grokking Database Fundamentals for Tech Interviews
Rate this course
Ask Author
Contribute
Back to course home

0% completed

Vote For New Content
Introduction to Database Systems
Course Overview
Overview of Databases
Core Components of Database
Database Architectures
Relational Vs. Non-relational Databases
Data Storage in DBMS
Data Storage Fundamentals
File Organization in DBMS
Data Compression and Encoding
Quiz
Indexing in DBMS
Introduction to Database Indexes
Single Level Indexing
Tree-Based Indexing Techniques
Hash-Based Indexing
Bloom Filters
Quiz
Transaction Management
Understanding the Transaction
Atomicity
Consistency
Isolation
Durability
Quiz
Concurrency Control
Understanding the Concurrency Control
Optimistic vs. Pessimistic Concurrency Control
Lock-Based Concurrency Control
Timestamp-Based Concurrency Control
Multiversion Concurrency Control (MVCC)
Quiz
Fundamentals of Distributed Databases
Partitioning in Databases
Partitioning Types
Sharding in Databases
Distributed Query Processing
Quiz
Replication in Databases
Replication Topologies
Understanding the Consistency Models in Databases
The CAP Theorem and Its Implications
Quiz
Understanding the Consensus
Consensus algorithms
Leader Election Strategies
Quiz
Understanding the Fault Tolerance
Logging Mechanisms in Databases
Checkpointing and Recovery Basics
Coordinated Recovery in Distributed Systems
High Availability Through Replication and Failover
Ensuring Data Resilience: Redundancy, Mirroring, and Recovery
Quiz
Introduction to NoSQL
Key-Value Stores
Document-Oriented Databases
Column-Family and Wide-Column Stores
Graph Databases
Quiz
Quora System Design & Database Design
TikTok System Design & Database Design
Airbnb System Design & Database Design
Snapchat System Design & Database Design
Timestamp-Based Concurrency Control

What is Timestamp-Based Concurrency Control?

Timestamp-based concurrency control is a technique used in databases to ensure that transactions are executed in a serializable order based on their timestamps. Each transaction is assigned a unique timestamp when it starts, which determines its logical order. Transactions must follow this order to prevent conflicts and ensure consistency.

  • Key Idea: Transactions are executed as if they were processed sequentially, based on their timestamps.
  • Guarantee: This method ensures serializability, which means the results of concurrent transactions are the same as if they were executed one after another.

Key Concepts in Timestamp-Based Concurrency

  • Transaction Timestamp (TS):

    • A unique identifier assigned to each transaction at its start time.
    • Ensures the logical order of execution.
  • Read Timestamp (RTS) and Write Timestamp (WTS):

    • Associated with each data item in the database.
    • RTS: The highest timestamp of any transaction that successfully read the data.
    • WTS: The highest timestamp of any transaction that successfully wrote to the data.

How Timestamp Ordering Works

The flowchart illustrates the process of timestamp-based ordering:

Image
  1. Transaction Begins:

    • A transaction is initiated and assigned a unique timestamp (e.g., based on the system clock).
  2. Validation Phase:

    • Before execution, the transaction checks for conflicts with other transactions based on timestamps.
    • Validation Logic:
      • If a transaction's timestamp is lower than another transaction's timestamp, it must execute before the conflicting transaction.
      • If the condition is not met, the transaction is rolled back or restarted.
  3. Execution Phase:

    • If validated, the transaction proceeds to execute its operations (read/write).
    • During execution:
      • Read Operation: Allowed if the transaction's timestamp is greater than or equal to the data's WTS.
      • Write Operation: Allowed if the transaction's timestamp is greater than or equal to the data's RTS.
  4. Conflict Resolution:

    • If a conflict is detected during validation or execution:
      • A conflict resolution strategy is applied.
      • The conflicting transaction may be aborted and restarted with a new timestamp.
  5. Successful Execution:

    • If no conflicts occur, the transaction successfully completes and updates the database.

How Read and Write Operations Work

  • Read Operation:

    • If a transaction's timestamp (TS) is ≥ WTS of the data item:
      • The transaction is allowed to read, and the RTS of the data is updated.
    • If TS is < WTS:
      • The transaction is aborted because it is trying to read outdated data.
  • Write Operation:

    • If TS is ≥ RTS and ≥ WTS:
      • The transaction writes to the data, and the WTS is updated.
    • If TS is < RTS:
      • The transaction is aborted to prevent overwriting data read by newer transactions.

Advantages of Timestamp-Based Concurrency Control

  • No Deadlocks: As no locks are used, the system avoids deadlocks entirely.

  • Ensures Serializability: Transactions are processed logically in the order of their timestamps, maintaining consistency.

  • Simple Conflict Resolution: Conflicts are easily detected and resolved by aborting the conflicting transaction.

Disadvantages of Timestamp-Based Concurrency Control

  • High Rollback Rates: Transactions with outdated timestamps may frequently fail and need to restart, leading to wasted resources.

  • Starvation: Older transactions might repeatedly get aborted if newer transactions conflict with them.

  • Overhead: Maintaining timestamps and checking read/write conditions add computational overhead.

Example Scenario of Online Ticket Booking System

  • Transaction A starts at 10:00 AM and tries to read the available tickets.
  • Transaction B starts at 10:01 AM and books one ticket, reducing availability.
  • Transaction A tries to book tickets after reading outdated data. The system detects a conflict and rolls back Transaction A to prevent inconsistency.
Lock-Based Concurrency Control
Multiversion Concurrency Control (MVCC)
Mark as Completed

On this page

What is Timestamp-Based Concurrency Control?

Key Concepts in Timestamp-Based Concurrency

How Timestamp Ordering Works

How Read and Write Operations Work

Advantages of Timestamp-Based Concurrency Control

Disadvantages of Timestamp-Based Concurrency Control

Example Scenario of Online Ticket Booking System